import java.util.*;

/**
 * @author VernHe
 * @date 2021年04月22日 13:55
 */
public class Solution_078 {
    public static void main(String[] args) {
        Solution_078 solution = new Solution_078();
        List<List<Integer>> subsets = solution.subsets(new int[]{1, 2, 2});
        System.out.println(subsets);
    }

    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Deque<Integer> path = new LinkedList<>();

        // 顺序剪枝，先排序
        Arrays.sort(nums);
        result.add(new ArrayList<>(path));
        select(nums, 0, path, result);

        return result;
    }

    private void select(int[] nums, int begin, Deque<Integer> path, List<List<Integer>> result) {
        // 递归基，结束递归
        if (begin == nums.length) {
            return;
        }

        for (int i = begin; i < nums.length; i++) {
            // 剪枝
            if (i > begin && nums[i] == nums[i - 1]) {
                continue;
            }
            // 选择后保存路径
            path.addLast(nums[i]);
            result.add(new ArrayList<>(path));
            // 继续往后选择
            select(nums, i + 1, path, result);
            // 能来到这里说明发生了【回溯】
            path.removeLast();
        }
    }
}
